'''
SearchList. A set of classes for expressing searchable lists of elements.
Copyright (C) 2006  Jonathan Claggett

This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the Free
Software Foundation; either version 2.1 of the License, or (at your option) any
later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more
details.

You should have received a copy of the GNU Lesser General Public License along
with this library; if not, write to the Free Software Foundation, Inc., 51
Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

You may contact the author at <jonathan@claggett.org>
'''
if __debug__: import pdb

# Searching Exceptions
class SearchListError(Exception):
    pass

class SearchItem(object):
    '''
    The SearchItem class provides the bottom level of a search list hierarchy.
    It impliments all of the same 'public' methods as the SearchList class.
    '''
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.reset()

    def keys(self):
        return [self.key]

    def has_key(self, key):
        return key == self.key

    def find(self, key=None):
        if self.ready and self.key == key:
            self.ready = False
            return self.value
        else:
            self.reset()
            return None

    def reset(self):
        self.ready = True

class SearchList(object):
    '''
    The SearchList class provides a reasonably expressive set of rules for
    describing the valid order of multiple child search lists.
    
    Child lists are defined to be in order or random, have minimum and maximum
    number of occurrences of each item in the list, and have minimum and
    maximum number of all occurrences of items from the list.
    '''

    def __init__(self,
        items=(),
        ordered=True,
        min_occur=None,
        max_occur=None,
        min_total=None,
        max_total=None):

        self.ordered = ordered

        # Build a protected list of items in which any non-searchable items are
        # wrapped within a SearchItem. This code assumes that any
        # non-searchable items will have an appropriate get_name() method.
        new_items = []
        for item in items:
            if not isinstance(item, (SearchList, SearchItem)):
                item = SearchItem(key=item.get_name(), value=item)
            new_items.append(item)
        self.items = new_items

        # min and max data validation.
        assert min_occur is None or min_occur >= 0
        assert min_total is None or min_total >= 0

        assert max_occur is None or max_occur > 0
        assert max_total is None or max_total > 0

        assert None in (min_occur, max_occur) or min_occur <= max_occur
        assert None in (min_total, max_total) or min_total <= max_total

        self.min_occur = min_occur
        self.max_occur = max_occur
        self.min_total = min_total
        self.max_total = max_total

        # Build a key mapping of the keys of child items to their index in the
        # list of items.
        self.keymap = {}
        for index, item in enumerate(self.items):
            for key in item.keys():
                self.keymap.setdefault(key, []).append(index)

        # Use the keymap's keys() and has_key() functions.
        self.keys = self.keymap.keys
        self.has_key = self.keymap.has_key

        if self.ordered:
            if self.min_occur is not None and self.min_occur > 0 \
              and len(self.items) > 0:
                # In an ordered, required list of items, only the first item's
                # keys are needed.
                self.keys = self.items[0].keys
                self.has_key = self.items[0].has_key

            self.next_index = self.next_ordered_index
        else:
            self.next_index = self.next_unordered_index

        # Get ready for incoming keys.
        self.resetable = True
        self.reset()

    def reset(self):
        if not self.resetable: return

        self.resetable = False

        if self.min_occur is not None and self.min_occur > 0:
            self.unmatched_items = len(self.items) 
        else:
            self.unmatched_items = 0

        self.found_occur = [ 0 for x in range(len(self.items)) ]
        self.found_total = 0
        self.ordered_index = 0
        self.active_index = None

        for item in self.items:
            item.reset()

    def find(self, key=None):

        # XXX This should never happen. protect against matching too many
        # items.
        assert self.max_total is None \
          or self.max_total > self.found_total

        self.resetable = True
        value = None

        while key is not None:
            if self.active_index is not None:
                value = self.find_in_item(self.active_index, key)

                if value is not None: # i.e,. the key matched...
                    key = None # erase the key.
                else:
                    # The key wasn't matched. Therefore, this search list has
                    # completed so we increase the totals and move on.
                    self.found_occur[self.active_index] += 1
                    if self.min_occur is not None \
                      and self.min_occur == self.found_occur[self.active_index]:
                        self.unmatched_items -= 1

                    self.found_total += 1
                    if self.max_total is not None \
                      and self.max_total <= self.found_total:
                        key = None # We're done. Erase this key.
                    else:
                        # Time to find the next active_index.
                        self.active_index = None

            else: # Find the next active_index.
                self.active_index = self.next_index(key)
                if self.active_index is None:
                    # No active_index was found so this search list is done.
                    key = None

        # If we didn't find a value for the key, check to insure that the
        # minimums for this search list have been met. Note that if a min_total
        # is not specified (i.e., min_total is None) then require that the
        # minimum occurences for each item of the search list are met.
        if value is None:

            # If there is still an active_index, then give that item a chance
            # to clean up and report errors if appropriate.
            if self.active_index is not None:
                self.items[self.active_index].find(key)

            try:
                if self.min_total is not None:
                    if self.min_total > self.found_total:
                        raise SearchListError, "Too few total items."
                elif self.min_occur is not None:
                    if self.unmatched_items > 0:
                        raise SearchListError, "Too few items."
            finally:
                # Clean up and prepare for future keys.
                self.reset()

        return value

    def find_in_item(self, index, key):
        try:
            return self.items[index].find(key)
        except:
            self.reset()
            raise

    def next_ordered_index(self, key):
        # Start with the next item if max_occur has been reached for the
        # current item.
        if self.max_occur is not None and self.max_occur <= \
          self.found_occur[self.ordered_index]:
            self.ordered_index += 1

        # Loop through each item trying to find the key's match.  The first
        # item to match becomes the next active item.
        for index in range(self.ordered_index, len(self.items)):
            if self.items[index].has_key(key):
                # The key matched and so this is the new active index.
                self.ordered_index = index
                return index
            elif self.min_occur is not None \
              and self.min_occur > self.found_occur[index]:
                # The key didn't match and we needed it so we give up on the
                # key and end this search.
                return None

        return None

    def next_unordered_index(self, key):
        # Use the keymap to find the list of possible matching items.  The
        # first matching item from the list that has less than max_occur
        # matches, becomes the next active item.
        for index in self.keymap.get(key, []):
            if self.max_occur is None \
              or self.max_occur > self.found_occur[index]:
                return index

        return None

# Convenience functions. These wrap around SearchList and provide common
# default search parameters.

def All(*items):
    '''
    Specify all items once in any order. 
    '''
    return SearchList( items,
        ordered = False,
        min_total = None,
        max_total = None,
        min_occur = 1,
        max_occur = 1 )

def Any(*items):
    '''
    Specify zero or more occurences of each item in any order.
    '''
    return SearchList( items,
        ordered = False,
        min_total = None,
        max_total = None,
        min_occur = None,
        max_occur = None )

def One(*items):
    '''
    Choose only one item from the search list.
    '''
    return SearchList( items,
        ordered = False,
        min_total = 1,
        max_total = 1,
        min_occur = None,
        max_occur = None )

def Seq(*items):
    '''
    Specify all items once in order.
    '''
    return SearchList( items,
        ordered = True,
        min_total = None,
        max_total = None,
        min_occur = 1,
        max_occur = 1 )

# Unit Testing
if __debug__:

    import unittest
    class TestSearchList(unittest.TestCase):
        @staticmethod
        def make_items(str):
            class NamedObject(object):
                def __init__(self, name): self.name = name
                def get_name(self): return self.name

            return [ NamedObject(letter) for letter in str ]
                
        def test_all(self):
            sl = All(*self.make_items('abc'))

            self.assertEqual('c', sl.find('c').get_name())
            self.assertEqual('b', sl.find('b').get_name())
            self.assertEqual('a', sl.find('a').get_name())
            self.assertEqual(None, sl.find('c'),)

        def test_any(self):
            sl = Any(*self.make_items('abc'))

            self.assertEqual('b', sl.find('b').get_name())
            self.assertEqual('c', sl.find('c').get_name())
            self.assertEqual('c', sl.find('c').get_name())
            self.assertEqual('a', sl.find('a').get_name())
            self.assertEqual('c', sl.find('c').get_name())
            self.assertEqual(None, sl.find('d'),)

        def test_one(self):
            sl = One(*self.make_items('abc'))

            self.assertEqual('b', sl.find('b').get_name())
            self.assertEqual(None, sl.find('d'),)

        def test_seq(self):
            args = self.make_items('abc')
            args.append( Any(*self.make_items('def') ) )

            sl = Seq(*args)

            self.assertEqual('a', sl.find('a').get_name())
            self.assertEqual('b', sl.find('b').get_name())
            self.assertEqual('c', sl.find('c').get_name())
            self.assertEqual('e', sl.find('e').get_name())
            self.assertEqual('f', sl.find('f').get_name())
            self.assertEqual('f', sl.find('f').get_name())
            self.assertEqual('f', sl.find('f').get_name())
            self.assertEqual('d', sl.find('d').get_name())
    
    if __name__ == '__main__':
        unittest.main()

# vim: ai et sw=4 ts=4
